package algorithms.sorts;

import algorithms.Utils;

import java.util.Arrays;
import java.util.List;


public class BucketSort {
    public static void main(String[] args) {
        //int[] arr = Utils.randomArray(100000000, -2000, 2000);
        int[] arr = Utils.randomArray(100000000, -10000, 10000);
        List<?> before = Arrays.asList(arr);
        //System.out.println(Arrays.toString(arr));
        long start = System.currentTimeMillis();
        System.out.println("bucketSort start:" + start);
        bucketSort(arr);

        long end = System.currentTimeMillis();
        System.out.println("  bucketSort end:" + end);
        System.out.println("  bucketSort use:" + (end - start));
        System.out.println(Utils.isAscend(arr));
        List<?> after = Arrays.asList(arr);
        System.out.println(before.containsAll(after));
    }


    private static void bucketSort(int[] arr) {
        int[] minAndMax = minAndMax(arr);
        int min = minAndMax[0];
        int max = minAndMax[1];

        int len = ((max - min) >> 4) + 1;

        Bucket[] buckets = new Bucket[len];

        for (int e : arr) {
            int index = (e - min) >> 4;
            Bucket bucket = buckets[index];
            if (bucket == null) {
                bucket = new Bucket();
                buckets[index] = bucket;
            }
            bucket.grow();
        }
        for (int e : arr) {
            int index = (e - min) >> 4;
            Bucket bucket = buckets[index];
            bucket.add(e);
        }


        int i = 0;
        for (Bucket bucket : buckets) {
            if (bucket == null) continue;
            HeapSort.heapSort(bucket.elements());
            for (int e : bucket.elements()) {
                arr[i++] = e;
            }
        }
    }

    private static int[] minAndMax(int[] arr) {
        int minIdx = 0, maxIdx = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[minIdx]) {
                minIdx = i;
            } else if (arr[i] > arr[maxIdx]) {
                maxIdx = i;
            }
        }
        int min = arr[minIdx];
        int max = arr[maxIdx];
        return new int[]{min, max};
    }


    /**
     * 桶结构，避免使用List
     */
    static class Bucket {
        private int size = 0;
        private int index = 0;
        private int[] elements;

        Bucket() {

        }

        void grow() {
            if (elements != null) throw new IllegalStateException("元素已添加,无法修改容量");
            size++;
        }

        int[] elements() {
            return elements;
        }

        boolean add(int e) {
            if (elements == null) elements = new int[size];
            if (index == size) return false;
            elements[index++] = e;
            return true;
        }


    }
}